package chapter02;

public class Exist79 {
    /**
     * 深度优先
     * 先尝试每一个位置作为待匹配字符串第一个字符的起始点 row->[0,m] col->[0,n]
     * process(chw,row,col,pos)  从[row,col]搜索匹配 chs下标为pos字符
     * 每一个位置都只能使用一个 用一个等规模数组记录[row,col]是否已使用
     * 递归出口
     *  1).pos==chw.length
     *      return true
     *  2).row<0||row==board.length||col<0||col==board[0].length
     *      return false
     *  3).其他情况
     *     a).chs[pos]和[row][col]相等并且该位置未使用 chs[pos]==[row][col]&&!used[row][col]
     *        先将该位置标记已使用 used[row][col]=true
     *        尝试相邻同行同列  res=false
     *         res|=process(chw,row,col+1,pos+1);
     *         res|=process(chw,row,col-1,pos+1);
     *         res|=process(chw,row-1,col,pos+1);
     *         res|=process(chw,row+1,col,pos+1);
     *         如果res为false说明[row][col]位置不适合  重新标为未使用used[row][col]=false
     *         return res
     *     b).否则 说明不匹配 直接返回
     *         return false
     */
    boolean[][] isUsed;
    public boolean exist(char[][] board, String word) {
        isUsed=new boolean[board.length][board[0].length];
        char[] chw=word.toCharArray();
        for(int row=0;row<board.length;row++){
            for(int col=0;col<board[0].length;col++){
                if(process(board,chw,row,col,0)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean process(char[][] board,char[] chw,int row,int col,int pos){
        if(pos==chw.length){
            return true;
        }
        if(row<0||row==board.length||col<0||col==board[0].length){
            return false;
        }
        if(board[row][col]==chw[pos]&&!isUsed[row][col]){
            boolean res=false;
            isUsed[row][col]=true;
            res|=process(board,chw,row,col+1,pos+1);
            res|=process(board,chw,row,col-1,pos+1);
            res|=process(board,chw,row-1,col,pos+1);
            res|=process(board,chw,row+1,col,pos+1);
            if(!res){
                isUsed[row][col]=false;
            }
            return res;
        }
        return false;
    }
}
